package leetcode.N501_N600;

import java.util.HashMap;
import java.util.Map;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/19 2:43 下午
 */
public class N567 {

    public static void main(String[] args) {
        String s2 = "eidbaooo";
        String s1 = "ab";
        System.out.println(checkInclusion(s1, s2));
    }

    public static boolean checkInclusion(String s1, String s2) {
        // 输入校验
        if (s1 == null) {
            return true;
        }
        if (s2 == null) {
            return false;
        }
        if (s1.length() == 0) {
            return true;
        }
        if (s2.length() == 0 || s2.length() < s1.length()) {
            return false;
        }
        // 构建基准映射
        Map<Character, Integer> sample = new HashMap<>(s1.length());
        for (char c : s1.toCharArray()) {
            Integer i = sample.get(c);
            if (i == null) {
                sample.put(c, 1);
            } else {
                sample.put(c, ++i);
            }
        }
        // 获取s2长度为s1.length的映射
        char[] s2Array = s2.toCharArray();
        Map<Character, Integer> s3Mapping = new HashMap<>(s1.length());
        for (int i = 0; i < s1.length(); i++) {
            char temp = s2Array[i];
            Integer val = s3Mapping.get(temp);
            if (val == null) {
                s3Mapping.put(temp, 1);
            } else {
                s3Mapping.put(temp, ++val);
            }
        }
        if (sample.equals(s3Mapping)) {
            return true;
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            // 移除最右元素
            // 加入最左元素
            char c = s2.charAt(i);
            Integer val = s3Mapping.get(c);
            if (val == null) {
                s3Mapping.put(c, 1);
            } else {
                s3Mapping.put(c, ++val);
            }
            char c1 = s2.charAt(i - s1.length());
            int i1 = s3Mapping.get(c1) - 1;
            if (i1 == 0) {
                s3Mapping.remove(c1);
            } else {
                s3Mapping.put(c1, i1);
            }
            if (sample.equals(s3Mapping)) {
                return true;
            }
        }
        return false;
    }

}
